package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.Arrays;

/**
 * 描述：
 * 有一个整数数组 nums ，和一个查询数组 requests ，其中 requests[i] = [starti, endi] 。第 i 个查询求 nums[starti] + nums[starti + 1] + ... + nums[endi - 1] + nums[endi] 的结果 ，starti 和 endi 数组索引都是 从 0 开始 的。
 * <p>
 * 你可以任意排列 nums 中的数字，请你返回所有查询结果之和的最大值。
 * <p>
 * 由于答案可能会很大，请你将它对 109 + 7 取余 后返回
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-sum-obtained-of-any-permutation
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author 🧑 ‍wanwei
 * @since 2023-01-12 17:20
 */
public class CQ1589 {

    public static void main(String[] args) {
        //统计出查询序列 查询的所有坐标 按照出现频率排序 同时按照顺序取数组值 这样就能保证拿到的是最大的值
        int[] nums = {272111111,837511111,837511111,837511111,837511111,837511111,837511111};
        int[][] requests = {{1,3},{0,1},{1,4}};
        System.out.println(maxSumRangeQuery(nums, requests));

    }

    public static int maxSumRangeQuery(int[] nums, int[][] requests) {
        int[] index = new int[nums.length];
        for (int i = 0; i < requests.length; i++) {
            int start = requests[i][0];
            int end = requests[i][1];
            for (int j = start; j <= end; j++) {
                index[j]++;
            }
        }

        //将index排序
        Arrays.sort(index);
        Arrays.sort(nums);

        int mod = (int) (Math.pow(10, 9) + 7);

        int value = 0;

        for (int i = index.length-1; i >= 0; i--) {
            if (index[i] == 0) {
                break;
            }
            value += nums[i] * index[i];
            if (value > mod) {
                value = value%mod;
            }
        }
        return value;
    }
}
